It is well known that computers and computing technology have been a great contribution to the advancement of human civilization in the last several decades. Computer technology has enabled digital problem solving and data analysis much more rapidly than humans can typically perform manually. In addition, persistent electronic data exchange available through computer networking has revolutionized worldwide communication, enabling systems such as e-mail and Instant Messaging, as well as enabling communication infrastructure supporting the Internet and providing a backbone for the World Wide Web.
As computer networks grow and sub-net works of various flavors form within them, sophisticated analysis tools have developed in an effort to optimize performance and effectiveness of these networks. One example is graph partitioning analysis. In mathematics, graph partitioning involves analyzing a graph (comprising nodes or vertices and connections, or edges, between the vertices) and identifying portions of the graph that have few connections with other portions thereof. Certain assumptions about a portion of the graph having these qualities are often appropriate. For instance, depending on what structure the mathematical graph represents (see below), such a portion of the graph could represent discussions centered on a common topic of interest, communications between a group of friends, ‘chat buddies’ or business colleagues, parallel computing processes having common data dependencies, a set of web pages visited interconnected by a set of links, and so on.
A graph typically comprises a set of vertices (or nodes) and edges (interconnections between the vertices). One example of a graph can comprise a compiler network, where individual computers, servers, processors, mainframes, data stores, databases and so forth, comprise graph vertices, and communication links between the vertices comprise graph edges. In such an ex ample, graph partitioning can involve analyzing compiler access to a set of databases to map collisions in data usage. Such a map can be useful to plan parallel processing that minimizes such collisions, as a particular example.
As a mathematical entity, a graph can represent various practical structures (e.g., computer networks, social networks, inter-personal interactions, trend analysis, online search analysis, etc.). Furthermore, applications for graph analysis can be even more diverse than the numerous structures such graphs can represent. In general, however, graph partitioning follows a set of rules, based on identifying relatively isolated portions of the graph (having few external edges). Optimized graph partitioning often involves identifying these isolated portions when given a starting point within the graph. Meaningful interpretation of the analysis can typically be left to higher level structures (e.g., computer programs) that make certain assumptions about macroscopic systems represented by the graph, enabling the graph partitioning problem to be independent of those systems. Accordingly, graph partitioning algorithms can be applied often without significant modification for an under tying application, yielding a robust and diversified tool for solving many problems pertaining to macroscopic interactions.